Computer networks, such as the Internet, have revolutionized the way in which people obtain information. For example, modern computer networks support the use of e-mail communications for transmitting information between people who have access to the computer network. Increasingly, systems are being developed to enable the exchange of data over a network that has a real-time component. For example, a video stream may be transmitted between computers connected by a network such that network conditions may affect how the information is presented to the user. Data is generally transmitted over a computer network in packets. Unfortunately, packet loss occurs when one or more packets being transmitted over the computer network fail to reach their destination. A number of factors may cause packet loss: an over utilized network, signal degradation, faulty hardware, and so on. When packet loss occurs, performance issues may become noticeable to the user. For example, in the context of a video stream, packet loss may result in “artifacts” or distortions that are visible in a sequence of video frames.
Network packet loss is common. It happens on the public Internet, DSL, Cable, wireless local area network (WLAN), 3G wireless, and many other kinds of networks. The estimated packet loss rate on the Internet is 5%, and some wireless networks may have packet loss of over 10%. Reliable network transmission protocols, such as Transmission Control Protocol (TCP), will resend a packet if the transmission medium drops the packet, thus guaranteeing packet delivery. Unreliable protocols, such as User Datagram Protocol (UDP), do not guarantee packet delivery and do not resend dropped packets. Resending packets takes time and consumes additional bandwidth. Due to the real-time nature of video communication, video signals are often sent using unreliable protocols and therefore will suffer from network packet loss.
For real-time video communication, a sending endpoint sends video frames across a network to a receiving endpoint, sometimes at a rate of 20 to 30 frames per second or more. Frames are divided into packets based on the Maximum Transmission Unit (MTU) allowed by the network (e.g., 1500 bytes for Ethernet). A frame of video may be small enough to fit within one packet, or may be large enough to require many packets. For some video compressor/decompressors (codecs), if any of the packets in a frame is dropped, then the receiving endpoint must discard the whole frame due to missing data.
In addition, codecs often use a dependency structure to reduce the amount of video data that a sending endpoint transmits over the network. For example, a frame called an intra (I) frame is encoded in full based on its contents. Subsequent frames are compressed based on a delta (difference signal) from the previous frames. These frames are often called prediction (P) frames. Some codecs introduce even more complex dependency structures. For example, the codec may occasionally send special P-frames called super-prediction (SP-frames) that, as opposed to regular P-frames, do not depend on the immediately preceding P-frame or I-frame but rather on an older SP-frame or I-frame. The contents of such SP-frames typically are less correlated with the reference frame and thus carry more video data. Another type of frame is a between or bi-directional (B) frame that contains a delta from both a previous and a subsequent frame. These types of inter-frame dependencies reduce the amount of data that the sending endpoint transmits over the network, but the dependencies also exaggerate the effects of network packet loss. For example, if an I-frame is dropped, the receiving endpoint will be missing data for all subsequent P-frames that depend on the I-frame, and the user will see video artifacts until the next I-frame arrives. If network packet loss is 1%, a 10 packet I-frame has a 10% chance of getting dropped according to the following formula:PI=1−(1−P)N Where PI is the probability of losing an I-frame, P is the probability of losing any packet, and N is the number of packets in the frame. If an I-frame has a 10% chance of being dropped, then subsequent frames that depend on the I-frame have a 10% chance of having video artifacts, even if all of the subsequent frames arrive at the receiving endpoint correctly.
One traditional method of reducing the effects of packet loss is forward error correction (FEC). Forward error correction (FEC) is a system of error control for data transmission, whereby the sending endpoint adds redundant data to its messages that allows the receiving endpoint to detect and correct errors (within some bound) without the need to ask the sending endpoint for additional data. The advantage of forward error correction is that retransmission of data can often be avoided (at the cost of higher bandwidth requirements on average) and is therefore applied in situations where retransmissions are relatively costly or impossible, such as when transmitting real-time video data. Different FEC algorithms have different bandwidth requirements and provide different levels of protection against lost packets, so different forward FEC algorithms are suitable for different conditions.
Unfortunately, it is difficult for the sending endpoint to determine which FEC algorithm will provide the best video experience for a particular network connection. The sending endpoint also often has bandwidth and computational resource limitations that make efficient choice of FEC algorithms advantageous. In addition, many sending endpoints are responsible for sending video data to many different receiving endpoints simultaneously, such that determinations that are performed for each endpoint can become very costly in terms of resources available at the sending endpoint.